package com.zrf.base.knowledge.leetcode.editor.cn;

import javafx.concurrent.Worker;

/**
 * //实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
 * //
 * // 示例:
 * //
 * // Trie trie = new Trie();
 * //
 * //trie.insert("apple");
 * //trie.search("apple");   // 返回 true
 * //trie.search("app");     // 返回 false
 * //trie.startsWith("app"); // 返回 true
 * //trie.insert("app");
 * //trie.search("app");     // 返回 true
 * //
 * // 说明:
 * //
 * //
 * // 你可以假设所有的输入都是由小写字母 a-z 构成的。
 * // 保证所有输入均为非空字符串。
 * //
 * // Related Topics 设计 字典树
 * // 👍 448 👎 0
 *
 * @author zhouruifeng
 * @date 2020-11-03 07:13:57
 */
public class ImplementTriePrefixTree {
    public static void main(String[] args) {

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Trie {
        private TrieNode root;
        /**
         * Initialize your data structure here.
         */
        public Trie() {
            root = new TrieNode();
        }

        /**
         * Inserts a word into the trie.
         */
        public void insert(String word) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                if (!node.containsKey(c)) {
                    node.put(c, new TrieNode());
                }
                node = node.get(c);
            }
            node.setEnd(true);
        }

        /**
         * Returns if the word is in the trie.
         */
        public boolean search(String word) {
            TrieNode trieNode = searchPrefix(word);
            return trieNode != null && trieNode.isEnd();
        }

        public TrieNode searchPrefix(String word) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                if (node.containsKey(c)) {
                    node = node.get(c);
                } else {
                    return null;
                }
            }
            return node;
        }

        /**
         * Returns if there is any word in the trie that starts with the given prefix.
         */
        public boolean startsWith(String prefix) {
            TrieNode trieNode = searchPrefix(prefix);
            return trieNode != null;
        }
    }

    class TrieNode {
        private final  Integer SIZE = 26;
        private TrieNode[] links;
        private boolean end;

        public TrieNode() {
            links = new TrieNode[SIZE];
        }

        public boolean containsKey(char ch) {
            return links[ch - 'a'] != null;
        }

        public void put(char ch, TrieNode trieNode) {
            links[ch - 'a']= trieNode;
        }

        public TrieNode get(char ch) {
            return links[ch - 'a'];
        }

        public void setEnd(boolean end) {
            this.end = end;
        }

        public boolean isEnd() {
            return this.end;
        }
    }

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */
//leetcode submit region end(Prohibit modification and deletion)

}